// nfa.cpp
//
// Copyright (C) 2008  Maksim Sipos <msipos@mailc.net>
//
// This file is a part of the Ripe language project.
//
// Ripe is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

#include "util/standard.hpp"
#include <cstdio>
#include "util/nfa.hpp"
#include "util/mem.hpp"

using std::printf;

namespace Ripe {

// Does the given matching class match a given UniChar?
static inline bool nfa_match(NFAMatchingClass mc, UniChar c);

bool nfa_match(NFAMatchingClass mc, UniChar c)
{
  switch (mc.type){
    case ClassAny:
      return true;
    case ClassSingle:
      return c == mc.extra1;
    case ClassRange:
      return c <= mc.extra2 and c >= mc.extra1;
  }
  assert_never();
  return false;
}

NFANode::NFANode()
{
  extra = NULL;
}

NFANode::~NFANode()
{
}

void NFANode::activate(NFAState* state)
{
  // Add to the state's active list
  // TODO: It might occur that a same node is activated twice. This node will
  // be stepped twice, and an avalanche of duplication could occur. Therefore,
  // State should really have a Set instead of a Vector.
  state->active_nodes.append(this);
}

void NFANode::route(NFANode* node)
{
}

bool NFANode::terminating()
{
  return false;
}

void NFASplitNode::activate(NFAState* state)
{
  for (unsigned int i = 0; i < children.size; i++){
    children[i]->activate(state);
  }
}

void NFASplitNode::route(NFANode* node)
{
  children.append(node);
}

void NFANode::step(NFAState* state, UniChar event)
{
}

void NFACharNode::step(NFAState* state, UniChar event)
{
  bool match = false;
  for (uint32_t i = 0; i < match_classes.size; i++){
    if (nfa_match(match_classes[i], event)){
      match = true;
      break;
    }
  }

  // Truth table: (justification for xor below)
  //   negative   match   next->activate()?
  //     false    false       false
  //     false    true        true
  //     true     false       true
  //     true     true        false
  if (negative xor match)
    next->activate(state);
}

void NFACharNode::route(NFANode* node)
{
  next = node;
}

bool NFATermNode::terminating()
{
  return true;
}

void NFAState::step(UniChar event)
{
  unsigned int n = active_nodes.size;
  if (n == 0)
    return;

  // Make a duplicate of the active_nodes vector.
  NFANode** active_old = (NFANode**) mem_alloca(sizeof(NFANode*) * n);
  for (unsigned int i = 0; i < n; i++){
    active_old[i] = active_nodes[i];
  }
  active_nodes.clear();

  // Now step through each item in active_old
  for (unsigned int i = 0; i < n; i++){
    active_old[i]->step(this, event);
  }
}

bool NFAState::any()
{
  return active_nodes.size > 0;
}

}
